/*
 * @lc app=leetcode.cn id=79 lang=javascript
 *
 * [79] 单词搜索
 */

// @lc code=start
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  if (board.length === 0 || word.length === 0) {
    return fasle;
  }
  let rows = board.length;
  let cols = board[0].length;
  const directions = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
  ];

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      const result = dfs(board, i, j, 0);
      if (result) {
        return true;
      }
    }
  }

  return false;

  /**
   * @description: 递归查询字符
   * @param {[][]} board
   * @param {number} i
   * @param {number} j
   * @param {number} index
   * @return {boolean}
   */
  function dfs(board, i, j, index) {
    if (board[i][j] !== word[index]) {
      return false;
    } else if (index === word.length - 1) {
      return true;
    }
    let char = word[index];
    let result = false;
    board[i][j] = 0;

    for (const [dx, dy] of directions) {
      let newi = dx + i;
      let newj = dy + j;
      if (
        newi >= 0 &&
        newi < rows &&
        newj >= 0 &&
        newj < cols &&
        board[newi][newj] !== 0
      ) {
        const res = dfs(board, newi, newj, index + 1);
        if (res) {
          result = true;
          break;
        }
      }
    }

    board[i][j] = char;
    return result;
  }
};
// @lc code=end
